package com.zj.leetcode.medium.hash;

import java.util.HashMap;

/**
 * @program: algorithm
 * @description:
 * 连续数组
 * 525 contiguous-array
 * @author: Zhang Bo
 * @create: 2022-01-14 17:05
 **/
public class ContiguousArray{
    public static void main(String[] args) {

        int[] nums = {1,1,0,1,0,1,1,1};
        Solution solution = new ContiguousArray().new Solution();

        System.out.println(solution.findMaxLength(nums));

    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 对于前缀和应该怎么去做，
         * 就是用pre[i] 减去 pre[j] 得到想要的结果，
         * 根据怎么得到的结果值，来确定什么是key，什么是value；
         * 然后再去写代码。
         *
         *
         * @param nums
         * @return
         */
        public int findMaxLength(int[] nums) {
            if(nums.length < 2){
                return 0;
            }


            HashMap<Integer, Integer> map = new HashMap<>();
            map.put(0, -1);

            int bucket = 0;
            int max = 0;
            for (int i = 0; i < nums.length; i++) {
                if(nums[i] == 0){
                    bucket--;
                } else {
                    bucket++;
                }

                if(map.containsKey(bucket)){
                    max = Math.max(i - map.get(bucket), max);
                } else {
                    //取最长要else 去最短不要else
                    map.put(bucket, i);
                }

            }

            return max;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
